package org.misty.practices.algorithm.tree;

import java.nio.CharBuffer;

/**
 * 线索二叉树
 *
 * 使用叶子节点的空指针域保存索引信息，将树遍历转换成链表遍历
 */
public class TBiTree {
    private char data;
    private TBiTree left;
    private TBiTree right;
    private PointerTag lTag = PointerTag.Link;
    private PointerTag rTag = PointerTag.Link;
    private TBiTree pre;
    private PointerTag tag;

    public TBiTree() {
    }

    public TBiTree(char data) {
        this.data = data;
    }

    public TBiTree(TBiTree left, TBiTree right, boolean head) {
        this.left = left;
        this.right = right;
        if (head) this.tag = PointerTag.Head;
    }

    protected void setData(char c) {
        this.data = c;
    }

    protected void setLeft(TBiTree left) {
        this.left = left;
    }

    protected void setRight(TBiTree right) {
        this.right = right;
    }

    public char getData() {
        return this.data;
    }

    public TBiTree getLeft() {
        if (lTag == PointerTag.Thread) return null;
        return this.left;
    }

    public TBiTree getRight() {
        if (rTag == PointerTag.Thread) return null;
        return this.right;
    }

    @Override
    public String toString() {
        return "TBiTree{" + data + '}';
    }

    private TBiTree inThreading() {
        var head = new TBiTree();
        head.tag = PointerTag.Head;
        head.left = this; // 头节点left指向根节点

        pre = head; // 中序序列第一个节点left指向头节点
        inThreading0(this); // 索引化，结束后pre指向中序序列最后一个节点

        head.right = pre; // 头节点right指向最后一个节点
        pre.right = head; // 最后一个节点right指向头节点
        return head;
    }

    private void inThreading0(TBiTree p) {
        // pre在一次循环中表示前驱节点
        if (p != null) {
            System.out.println(p.data);
            inThreading0(p.left);
            if (p.left == null) { // 当前节点左子树与前驱节点关联
                p.lTag = PointerTag.Thread;
                p.left = pre;
            }
            if (pre != null && pre.right == null) { // 前驱节点右子树与当前节点关联
                pre.rTag = PointerTag.Thread;
                pre.right = p;
            }
            pre = p;
            inThreading0(p.right);
        }
    }

    public String inOrderTraverse() {
        var buffer = new StringBuilder();
        inOrderTraverse0(buffer);
        return buffer.toString();
    }

    private void inOrderTraverse0(StringBuilder buffer) {
        if (this.tag == PointerTag.Head) {
            var head = this;
            var p = head.left; // p指向根节点
            while (p != head) {
                while (p.lTag == PointerTag.Link) { // 找到第一个节点
                    p = p.left;
                }
                buffer.append(p.data);
                while (p.rTag == PointerTag.Thread && p.right != head) { // 如果p节点right是索引
                    p = p.right; // 通过索引遍历
                    buffer.append(p.data);
                }
                p = p.right; // 如果不是索引，则按常规方式遍历
            }
        }
    }

    public static TBiTree create(String seq) {
        var buffer = CharBuffer.wrap(seq);
        var tree = buffer.hasRemaining() ? create0(buffer) : null;
        if (tree != null) return tree.inThreading();
        return null;
    }

    private static TBiTree create0(CharBuffer buffer) {
        char ch = buffer.get();
        if (ch == '#') {
            return null;
        } else {
            var t = new TBiTree(ch);
            if (buffer.hasRemaining()) t.setLeft(create0(buffer));
            if (buffer.hasRemaining()) t.setRight(create0(buffer));
            return t;
        }
    }

    enum PointerTag {
        Link, Thread, Head,
    }

    public static void main(String[] args) {
        var tree = create("AB#D##C##");
        System.out.println(tree);
        System.out.println(tree.inOrderTraverse());
    }
}
